//
// Created by 123 on 2024/3/27.
//二叉排序树

#include <iostream>

using namespace std;

typedef struct BSNode {
    int data;
    BSNode *lchild;
    BSNode *rchild;
} BSNode, *BSTree;

//根据值，创建一个节点
BSNode *getBsNode(int e);

//插入
bool insertNode(BSTree &bsTree, int e);

//创建
BSTree creatBSTree(int arr[], int len);

//查
BSNode *searchBSTree_recursion(BSTree bsTree, int e);

BSNode *searchBSTree_no_recursion(BSTree bsTree, int e);

//删除
//删除中序后继
bool deleteBSTree_back(BSTree &bsTree, int e);

//获得后继结点
BSNode *getSuccessorNode(BSTree bsTree, BSTree &pre_child);

//中序遍历
void midOrderTraversal(BSTree tree);

int main() {
    int arr[9] = {5, 9, 3, 1, 8, 7, 2, 4, 10};
    BSTree bsTree = creatBSTree(arr, 9);

//    BSNode *node=searchBSTree_recursion(bsTree,0);
    BSNode *node = searchBSTree_no_recursion(bsTree, 1);
    if (node == NULL) {
        cout << "为空" << endl;
    } else {
        cout << "数据为：" << node->data << endl;
    }

    midOrderTraversal(bsTree);
    cout << endl;
    bool fa = deleteBSTree_back(bsTree, 9);
    cout << fa << endl;
    midOrderTraversal(bsTree);



}

void node_chain(BSTree &preNode, BSTree node, int e) {
    if (preNode->lchild != NULL && preNode->lchild->data == e) {
        preNode->lchild = node;
    }
    if (preNode->rchild != NULL && preNode->rchild->data == e) {
        preNode->rchild = node;

    }
}

bool deleteBSTree_back(BSTree &bsTree, int e) {
//    找到要删除的节点
    BSNode *node = bsTree;
    BSNode *pre_node = bsTree;
    while (node != NULL && node->data != e) {
        pre_node = node;
        if (e > node->data)
            node = node->rchild;
        else
            node = node->lchild;
    }
    if (node == NULL)
        return false;
//    若没有左子树，则直接等于右子树
    else if (node->lchild == NULL) {
        int val = node->data;
        node = node->rchild;
        node_chain(pre_node, node, val);
//        若没有右子树，则直接等于左子树
    } else if (node->rchild == NULL) {
//        BSNode *temp = node;
        int val = node->data;
        node = node->lchild;
        node_chain(pre_node, node, val);

//        free(temp);
    } else {
        //    找到中序的后继节点，改变要是删除点的值，算了自己画图想想吧
        BSNode *pre_child;
        BSNode *child = getSuccessorNode(node, pre_child);
        int val = node->data;
        node->data = child->data;
        int child_val = child->data;
        child = child->rchild;
//        连接节点用
        node_chain(pre_child, child, child_val);
        node_chain(pre_node, node, val);
    }
    return true;
}

BSNode *getSuccessorNode(BSTree bsTree, BSTree &pre_child) {
    pre_child = bsTree;
    BSNode *node = bsTree->rchild;
    while (node->lchild != NULL) {
        pre_child = node;
        node = node->lchild;
    }
    return node;
}


BSNode *searchBSTree_no_recursion(BSTree bsTree, int e) {
    while (bsTree != NULL && bsTree->data != e) {
        if (e > bsTree->data)
            bsTree = bsTree->rchild;
        else
            bsTree = bsTree->lchild;
    }
    return bsTree;
}

BSNode *searchBSTree_recursion(BSTree bsTree, int e) {
    if (bsTree == NULL)
        return NULL;
    if (bsTree->data == e)
        return bsTree;
    else if (e > bsTree->data)
        return searchBSTree_recursion(bsTree->rchild, e);
    else
        return searchBSTree_recursion(bsTree->lchild, e);
}

BSTree creatBSTree(int arr[], int len) {
    BSTree bsTree;
    int i = 0;
    while (i < len)
        insertNode(bsTree, arr[i++]);
    return bsTree;
}

bool insertNode(BSTree &bsTree, int e) {
    if (bsTree == NULL) {
        bsTree = getBsNode(e);
        return true;
    }
    if (e == bsTree->data)
        return false;
    else if (e < bsTree->data)
        return insertNode(bsTree->lchild, e);
    else
        return insertNode(bsTree->rchild, e);

//    if (e == bsTree->data)
//        return false;
//    if (e < bsTree->data) {
//        if (bsTree->lchild == NULL) {
//            bsTree->lchild = getBsNode(e);
//            return true;
//        }
//        insertNode(bsTree->lchild,e);
//    }
//    if (e > bsTree->data){
//        if(bsTree->rchild==NULL){
//            bsTree->rchild= getBsNode(e);
//            return true;
//        }
//        insertNode(bsTree->rchild,e);
//
//    }
//    return false;
}


BSNode *getBsNode(int e) {
    BSNode *node = (BSNode *) malloc(sizeof(BSNode));
    node->data = e;
    node->rchild = NULL;
    node->lchild = NULL;
    return node;
}

void midOrderTraversal(BSTree tree) {
    if (tree != NULL) {
        midOrderTraversal(tree->lchild);
        cout << tree->data << "     ";
        midOrderTraversal(tree->rchild);
    }
}